package sort;

import java.util.Arrays;

/**
 * 基数排序：Java
 *
 * @author
 * @date
 */

public class RadixSort {

	public static void main(String[] args) {
		int a[] = {53, 3, 542, 748, 14, 214, 154, 63, 616};
		System.out.println(Arrays.toString(a));

		//基数排序：
		//获取数组中的最大值，判断最大值有几位数
		//从个位开始对每一个数进行排序
		//再将排序后的数组覆盖原数组
		//再对十位进行排序
		//。。。依次往下结束
		int max = getMax(a);
		int i=1;
		while(max/i > 0){
			radixSort(a,i);
			//排序完之后往上一位进行排序
			i = i*10;
		}
		System.out.println(Arrays.toString(a));
	}

	private static int getMax(int[] a) {
		int max =a[0];
		for (int i = 1; i < a.length; i++) {
			if(max<a[i]){
				max = a[i];
			}
		}
		return max;
	}

	private static void radixSort(int[] a, int i) {
		//其实就是抽取特定位数的值，进行桶排序
		//桶排序原理就是：临时数组下标就是a[j]的值，临时数组的值就是这个值出现的个数
		//步骤：
		//1.创建临时数组
		int[] bucketArr = new int[10];
		//2.遍历原数组个位数，对出现次数进行统计。
		for (int j = 0; j <a.length ; j++) {
			int index = (a[j]/i)%10;
			bucketArr[index]++;
		}
		//3.查找规律如何将原数组与临时数组的数据一一对上，并放入输出的数组里
			//3.1 关系规律： 临时数组里从0-9是有大小顺序的，所以可以按照个数进行排序，也就是说，数组的值的累加就等于临时数组的长度。
		for (int j = 1; j <10; j++) {
			bucketArr[j] +=bucketArr[j-1];
		}
		int[] output = new int[a.length];
			//3.2 按照a[j]对应到临时数组的哪个位置的值，就代表是a[j]在输出数组的位置， 放入到输出数组中。
		//PS:因为是升序，所以随着bucket的值递减，存放到output的位置的顺序也是递减的，所以遍历原数组的顺序也要和存放的顺序一样，即倒序。
		for (int j = a.length-1; j >=0; j--) {
				//计算下标：个数-1
					//先找到a[j]对应的bucketArr的位置
				int index = bucketArr[(a[j]/i)%10] -1;
				output[index] = a[j];
				//这里放到output里面之后，对应的桶的值应该要减1，因为位置总数是一定的，用了必须减掉一个。
				bucketArr[(a[j]/i)%10]--;
		}
		//4.将输出的数组替换原数组。
		System.arraycopy(output,0,a,0,a.length);
	}
}